package first.niuke.midding;

/**
 * @ClassName NC83
 * @description:
 * @author: 荣燊
 * @create: 2021-06-24 21:40
 **/
public class NC83 {
    public static void main(String[] args) {
        double[] a = {-2.5,4,0,3,0.5,8,-1};
        // 子数组{3,0.5,8}是最大乘积
        System.out.println(maxProduct(a));
        // 子数组{4,0,3,0.5,8}是最大和
        System.out.println("----------------------------");
        System.out.println(maxProduct1(a));
    }



    /**
     * 又是一个求连续区间数组的问题，典型的动态规划问题。
     * 和求最大区间和 不同的是，如果我们依然尝试用dp[i]表示以a[i]结尾的子区间的最大成绩。
     * 会发现由于负数的存在，会导致乘法结果反转。dp[i-1]a[i]反倒变成了最小值，无法得到状态转移方程。
     * 沿着乘法的特性看，如果a[i]为负数，那么dpa[i]时，dp越大结果越小。dp越小结果越大。所以，我们只需要同时保存最大值和最小值，就可以写出状态转移方程了。
     * a[i] > 0时：
     * maxv[i] = max(a[i], a[i]*maxv[i-1])
     * minv[i] = min(a[i], a[i]*minv[i-1])
     * a[i] < 0时：
     * maxv[i] = max(a[i], a[i]*minv[i-1])
     * minv[i] = min(a[i], a[i]*maxv[i-1])
     * a[i]=0时，max和min肯定是0。
     */
    // 子数组的最大乘积
    public static double maxProduct(double[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        double maxS = arr[0];
        // 两个数组，同时保存最大值与最小值
        double[] maxv = new double[arr.length];
        double[] minv = new double[arr.length];
        maxv[0] = arr[0];
        minv[0] = arr[0];

        for (int i=1; i<arr.length; i++) {
            if (arr[i] > 0) {
                maxv[i] = Math.max(arr[i], arr[i]*maxv[i-1]);
                minv[i] = Math.min(arr[i], arr[i]*minv[i-1]);
            } else {
                maxv[i] = Math.max(arr[i], arr[i]*minv[i-1]);
                minv[i] = Math.min(arr[i], arr[i]*maxv[i-1]);
            }
            maxS = Math.max(maxv[i], maxS);
        }

        return maxS;
    }

    // 最大区间和,用dp[i]表示以a[i]结尾的子区间的最大和
    // 当 dp[i−1]>0 时：执行 dp[i]=dp[i−1]+nums[i]
    // 当 dp[i−1]≤0 时：执行 dp[i]=nums[i]
    public static double maxProduct1(double[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        double[] doubles = new double[arr.length];
        doubles[0] = arr[0];

        for (int i=1; i<arr.length; i++) {
            if (doubles[i-1] > 0) {
                doubles[i] = doubles[i-1] + arr[i];
            } else {
                doubles[i] = arr[i];
            }
        }

        double maxSum = arr[0];
        for (int i=1; i<arr.length; i++) {
            if (maxSum < doubles[i]) {
                maxSum = doubles[i];
            }
        }
        return maxSum;
    }
}
